package LeetCode._06小算法;
/*
    核心思路是我们 new 一个新的数组 preSum 出来，preSum[i] 记录 nums[0..i-1] 的累加和
    求给定区间的和[left,right]只需要计算pre[right+1] - pre[left]
    前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
 */
public class _03前缀数组 {
    class NumArray {
        int[] preSum;

        public NumArray(int[] nums) {
            //preSum[i] = nums[0..i-1]的和
            preSum = new int[nums.length + 1];
            //preSum[0] = 0,便于计算前缀和
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }

        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }
    }
}
